#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "str.h"

void InitString(String string)
{
	string[0] = '\0';
}

int StrAssign(String string, char *str)
{
	int len = strlen(str);
	if (len > MAXSTRLEN)
		return -1;
	for (int i = 0; i < len; i++)
		string[i] = str[i];
	string[len] = '\0';
	return 0;
}

void StrCopy(String string, String str)
{
	int len = StrLength(str);
	for (int i = 0; i < len; i++)
		string[i] = str[i];
	string[len] = '\0';
}

int StrEmpty(String string)
{
	return string[0] == '\0';
}

int StrCompare(String string, String str) // string>str 返回1 string=str 返回0 string<str 返回-1
{
	int result;
	int len1 = StrLength(string);
	int len2 = StrLength(str);
	if (len1 > len2)
		return 1;
	else if (len1 < len2)
		return -1;
	else
	{
		while (*string != '\0')
		{
			result = *string - *str;
			if (result != 0)
				break;
			string++;
			str++;
		}
		if (result > 0)
			return 1;
		else if (result < 0)
			return -1;
		return 0;
	}
}

int StrLength(String string)
{
	int len = 0;
	while (*string++ != '\0')
		len++;
	return len;
}

void StrConcat(String string, String str1, String str2)
{
	int len1 = StrLength(str1);
	int len2 = StrLength(str2);
	if (len1 + len2 <= MAXSTRLEN)
	{
		for (int i = 0; i < len2; ++i)
			string[len1 + i] = str2[i];
		string[len1 + len2] = '\0';
	}
	else if (len1 <= MAXSTRLEN) // str1能完全存放,str2需要截断存放
	{
		for (int i = 0; i < MAXSTRLEN - len1; ++i)
			string[len1 + i] = str2[i];
		string[MAXSTRLEN] = '\0';
	}
	for (int i = 0; i < len1; ++i)
		string[i] = str1[i];
}

int SubString(String string, String sub, int pos, int len)
{
	int s_len = StrLength(string);
	if (pos < 0 || len < 0)
		return -1;
	if (pos + len > s_len)
		return -2;
	for (int i = 0; i < len; i++)
		sub[i] = string[pos + i];
	sub[pos + len] = '\0';
	return 0;
}

void StrInsert(String string, int pos, String str)
{
	int len1 = StrLength(string);
	int len2 = StrLength(str);
	if (len1 + len2 > MAXSTRLEN)
	{
		//这种情况下str不能完全插入，只能插入MAXSTRLEN-len1个字符
		len2 = MAXSTRLEN - len1;
	}
	for (int i = len1 - 1; i >= pos; i--)
		string[i + len2] = string[i];
	for (int i = 0; i < len2; i++)
		string[pos + i] = str[i];
	string[len1 + len2] = '\0';
}

int StrDelete(String string, int pos, int len)
{
	int s_len = StrLength(string);
	if (pos < 0 || len < 0)
		return -1;
	if (pos + len > s_len)
		return -2;
	for (int i = pos + len; i < s_len; i++)
		string[i - len] = string[i];
	string[s_len - len] = '\0';
	return 0;
}

void StrClean(String string)
{
	string[0] = '\0';
}

int StringIndex(String string, String str, int pos)
{
	int i = pos, j = 0;

	if (pos < 0 || pos > StrLength(string))
		return -1;
	while (string[i] != '\0' && str[j] != '\0')
	{
		if (string[i] == str[j])
		{
			i++;
			j++;
		}
		else
		{
			i = i - j + 1; //回退j个匹配成功的字符位置并前移一个位置
			j = 0;
		}
	}
	if (str[j] == '\0')
		return i - j;
	else
		return -2;
}

int StringIndex2(String string, String str, int pos)
{
	int i = pos, j = 0, k = pos; // k变量记录主串匹配的起始位置

	if (pos < 0 || pos > StrLength(string))
		return -1;
	while (string[i] != '\0' && str[j] != '\0')
	{
		if (string[i] == str[j])
		{
			++i;
			++j;
		}
		else
		{
			++k;
			i = k;
			j = 0;
		}
	}
	if (str[j] == '\0') //模式串匹配完，表示匹配成功
		return k;
	else
		return -2;
}

int StrReplace(String string, String str1, String str2)
{
	int s_len = StrLength(string);
	int t_len = StrLength(str1);
	int v_len = StrLength(str2);
	int pos = 0, index;
	while (pos < s_len)
	{
		index = StringIndex(string, str1, pos);
		if (index == -2)
			return -1;
		pos = index;
		StrDelete(string, pos, t_len);
		StrInsert(string, pos, str2);
	}
	return 0;
}

//计算子串的Next数组
static void getNext(String sub, int *next)
{
	next[0] = -1;
	next[1] = 0;
	int i = 2, k = 0; //前一项的回退位置，开始next[2]的前一项next[1]的回退位置是0

	while (i < StrLength(sub))
	{
		if (k == -1 || sub[i - 1] == sub[k])
		{
			next[i] = k + 1;
			k++;
			i++;
		}
		else
			k = next[k];
	}
}
//计算子串的Nextval数组(优化后的Next数组)
static void getNextVal(String sub, int *nextval)
{
	nextval[0] = -1;
	nextval[1] = 0;
	int i = 2, k = nextval[1]; //前一项的回退位置，开始设置nextval[2]的回退位置等于nextval[1]
	int lenSub = StrLength(sub);

	while (i < lenSub)
	{
		if (k == -1 || sub[i - 1] == sub[k])
		{
			nextval[i] = k + 1;  //匹配成功则在前一项回退位置基础上+1
			k++;
			i++;
		}
		else
			k = nextval[k];
	}
}

// pos：从主串的pos位置开始匹配
int KMP(String str, String sub, int pos)
{
	int i = pos, j = 0;
	int lenStr = StrLength(str);
	int lenSub = StrLength(sub);

	if (pos < 0 || pos > StrLength(str))
		return -1;
	if (lenStr == 0 || lenStr == 0)
		return -2;

	int *next = malloc(sizeof(u_char) * lenSub);
	if (next == NULL)
		return -3;
	getNext(sub, next);

	while (i < lenStr && j < lenSub)
	{
		if (j == -1 || str[i] == sub[j])
		{
			++i;
			++j;
		}
		else
			j = next[j];
	}

	if (sub[j] == '\0')
	{
		free(next);
		return i - j;
	}
	else
	{
		free(next);
		return -4;
	}
}